# 49/100 二叉树-二叉树的最近公共祖先
# leetcode第236题: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/9
from typing import Optional

from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):
    res = TreeNode(None)

    def dfs(curr):
        nonlocal res
        if not curr:
            return False
        l = dfs(curr.left)
        r = dfs(curr.right)
        is_pq = curr.val == p.val or curr.val == q.val
        if l + r + is_pq >= 2:
            res = curr
        return l or r or is_pq

    dfs(root)
    return res.val if res else None


if __name__ == '__main__':
    print(True + False)  # True和False在加法中可以自动转换类型为int, True为1, False为0
    print(True + True)
    root1 = TreeConverter.list_to_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])

    inp = [{"root": root1, "p": TreeNode(5), "q": TreeNode(1)},
           {"root": root1, "p": TreeNode(5), "q": TreeNode(4)}, ]
    out = [3, 5, ]
    test.test_function(lowestCommonAncestor, inp, out)
